package com.xiaoyu.dp;

/**
 * @program: DS_and_A
 * @description: 爬楼梯   标准动态规划的题目
 *
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 * 注意：给定 n 是一个正整数。
 *
 * 输入： 2
 * 输出： 2
 * 解释： 有两种方法可以爬到楼顶。
 * 1.  1 阶 + 1 阶
 * 2.  2 阶
 *
 *
 * 动态规划: 内核--->记住一些值来方便以后的计算!!  "分步存储规划法"
 *    三步走:
 *     1.建立状态转移方程
 *          当已经知道f[1]~f[n-1]的值，然后想办法利用它们求得f[n]的值
 *     2.缓存并复用以往结果
 *          这一步不难，但是很重要。如果没有合适地处理，很有可能就是指数和线性时间复杂度的区别。
 *          ·缓存中间结果:也就是搞个数组之类的变量记录中间结果。
 *     3.按顺序从小到大算
 *          这里的"小"和"大"对应的是问题的规模，在这里也就是我们要从f(O)，f(1)，...到f(n）依次顺序计算
 *          ·按顺序从小往大算:也就是搞个for循环依次计算。
 *
 * @author: YuWenYi
 * @create: 2021-05-23 10:11
 **/
public class ClimbStairs_70 {

    public static int climbStairs(int n) {
      /*这个是正解,但是时间复杂度为n^2,太高了导致超时
      if(n == 2){
            return 2;
        }
        if (n == 1){
            return 1;
        }
        return climbStairs(n - 1)+climbStairs(n - 2);*/
        //改变版本的递归方法,使用一个memory数组去记录已经计算过的数字,这样就避免了非常多的不必要的计算
        int[] memo = new int[n + 1];
        return climbStairsMemo(n, memo);
    }
    public static int climbStairsMemo(int n,int[] memo){
        //如果在memo数组中这个数组已经被计算过了,那么就直接返回这个数字,而不必再去进行计算
        if (memo[n] > 0){
            return memo[n];
        }
        if (n == 1){
            return memo[n] = 1;
        } else if (n == 2){
            return memo[n] = 2;
        }else {
            memo[n] =  climbStairsMemo(n-1, memo) + climbStairsMemo(n-2, memo);
        }
        return memo[n];
    }

    //使用动态规划的方法去解题,这样的时间复杂度为On,空间也为On
    public static int climbStairs1(int n) {
        if (n == 1){
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }

    //上面的方法好是好,但是最后使用到的只有一个数值却需要浪费On的空间去解决,因此我们可以换个思路
    //使用滚动数组的方法,解决这个问题!
    public static int climbStairs2(int n) {
        if (n <= 2){
            return n;
        }
        int first = 1;
        int second = 2;
        int three = 0;
        for (int i = 3; i <= n; i++) {
            three = first+second;
            first = second;
            second = three;
        }
        return three;
    }

    public static void main(String[] args) {
        System.out.println(climbStairs1(2));
    }
}
